/**
 * 
 */
package string.passed2;

import java.util.Arrays;

/**
 * @author xyyi
 *
 */
public class ReverseWordsInString {

	/**
	 * a stirng like "i like you" to "you like i"
	 */
//	public void reverseWords(char[] words) {
//		if (words.length == 0)
//			return;
//		int slow = 0, fast = 0;
//
//		reverse(words, 0, words.length - 1);
//		while (fast < words.length && words[fast] == ' ') {
//			slow++;
//			fast++;
//		}
//		while (fast < words.length) {
//			if (words[fast] == ' ') {
//				reverse(words, slow, fast - 1);
//				while (fast < words.length && words[fast] == ' ') {
//					fast++;
//				}
//				slow = fast;
//			} else {
//				fast++;
//			}
//		}
//		if (slow < words.length - 1) {
//			reverse(words, slow, fast - 1);
//		}
//	}
//
//	private void reverse(char[] words, int start, int end) {
//		if (!(start >= 0 && end >= start))
//			return;
//		while (start < end) {
//			swap(words, start++, end--);
//		}
//	}
//
//	private void swap(char[] words, int i, int j) {
//		if (i < 0 || j < 0)
//			return;
//		char tmp = words[i];
//		words[i] = words[j];
//		words[j] = tmp;
//	}

	
    public String reverseWords(String s) {
    	if (s == null || s.isEmpty())
    		return s;
    	char[] words = s.toCharArray();
    	StringBuilder sb = new StringBuilder();
    	
    	reverse(words, 0, words.length - 1);
    	
    	int fast = 0, slow = 0;
    	//skip leading spaces
    	while (fast < words.length && words[fast] == ' ') {
    		fast++;
    		slow++;
    	}
    	while (fast < words.length) {
    		if (words[fast] == ' ') {
    			reverse(words, slow, fast - 1);
    			sb.append(Arrays.copyOfRange(words, slow, fast)).append(" ");
    			while (fast < words.length && words[fast] == ' ') {
    				fast++;
    			}
    			slow = fast;
    		}
    		else {
    			fast++;
    		}
    	}
    	if (slow < fast) {
    		reverse(words, slow, fast - 1);
    		sb.append(Arrays.copyOfRange(words, slow, fast));
    	}
    	else if (sb.length() > 0) {
    			sb.setLength(sb.length() - 1);
    	}
    
    	return sb.toString();
    }
    
    public String reverseWords1(String s) {
    	if (s == null || s.isEmpty())
    		return s;
    	char[] words = (" " + s.trim()).toCharArray();
    	StringBuilder sb = new StringBuilder();
    	
    	reverse(words, 0, words.length - 1);
    	
    	int fast = 0, slow = 0;

    	while (fast < words.length) {
    		if (words[fast] == ' ') {
    			reverse(words, slow, fast - 1);
    			sb.append(Arrays.copyOfRange(words, slow, fast)).append(" ");
    			while (fast < words.length && words[fast] == ' ') {
    				fast++;
    			}
    			slow = fast;
    		}
    		else {
    			fast++;
    		}
    	}
    	if (sb.length() > 0) {
    		sb.setLength(sb.length() - 1);
    	}
    
    	return sb.toString();
    }
    
    
    public void reverse(char[] arr, int begin, int end) {
    	if (begin < 0 || end < begin)
    		return;
    	while (begin < end) {
    		swap(arr, begin++, end--);
    	}
    }
    
    public void swap(char[] arr, int i, int j) {
    	if (i < 0 || j < 0)
    		return;
    	arr[i] ^= arr[j];
    	arr[j] ^= arr[i];
    	arr[i] ^= arr[j];
    }
	
	
	/**
	 * 
	 */
	public ReverseWordsInString() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ReverseWordsInString rws = new ReverseWordsInString();
		String str = " I  like you    ";
		char[] words = str.toCharArray();

		//rws.reverseWords(words);
		System.out.printf("'%s' : '%s'", str, new String(words));
	}

}
